<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>779. 第K个语法符号</title>
  </head>
  <body>
    <script>
      //     我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

      // 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
      // 给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

      // 示例 1:

      // 输入: n = 1, k = 1
      // 输出: 0
      // 解释: 第一行：0
      // 示例 2:

      // 输入: n = 2, k = 1
      // 输出: 0
      // 解释:
      // 第一行: 0
      // 第二行: 01
      // 示例 3:

      // 输入: n = 2, k = 2
      // 输出: 1
      // 解释:
      // 第一行: 0
      // 第二行: 01
      //

      // 提示:

      // 1 <= n <= 30
      // 1 <= k <= 2n - 1

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/k-th-symbol-in-grammar
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
      /**
       * @param {number} n
       * @param {number} k
       * @return {number}
       */
      var kthGrammar = function (n, k) {
        // let str = '0'
        // debugger
        // for (let i = 1; i < n; i++) {
        //   let newStr = ''
        //   for (let j = 0; j < str.length; j++) {
        //     if (str[j] === '0') {
        //       newStr += '01'
        //     }
        //     if (str[j] === '1') {
        //       newStr += '10'
        //     }
        //   }
        //   str = newStr
        // }
        // return str[k - 1]

        if (N === 1) return 0

        // 计算当前行的长度：2的N-1次方
        var length = 2 ** (N - 1)

        // 如果K大于长度的一半，就是K所在位置是后半段
        if (K > length / 2) {
          // 先得到上一行的值，位置是K相对于后半段的位置
          var val = kthGrammar(N - 1, K - length / 2)

          // 然后把值反过来
          return val === 0 ? 1 : 0
        }
        // 否则前半部分
        else {
          // 值就是上一行K位置的值
          return kthGrammar(N - 1, K)
        }
      }
      console.log(kthGrammar(2, 1))
    </script>
  </body>
</html>
